1. Field of the Invention
The present invention relates to a progressive coding/decoding method of three-dimensional (3D) mesh data used in the fields of motion picture experts group-4 synthetic and natural hybrid coding (MPEG-4 SNHC), virtual reality modelling language (VRML) and the like.
2. Description of the Related Art
In transmitting 3D objects composed of 3D mesh data, it is very important to progressively restore transmitted data as well as to effectively code the 3D mesh data. In the event that a data error is generated due to a transmission path error, a progressive restoration would allow transmitted data to be partially restored and minimize the amount of mesh data to be retransmitted. The progressive restoration method which is robust against such communication path errors can be effectively used in wireless communications or low transmission rate communications. The purposes of the present invention are to construct connectivity, geometry and photometry necessary for progressively coding 3D mesh data and providing resilience against data errors, and to propose a coding/decoding method of the same.
The definitions of terms used in the art related to the invention will be first described as follows.
Polygonal mesh: A polygonal mesh is defined by coordinates (geometry) on a 3D space of vertices, the relationship (connectivity) between the respective faces and the vertices forming the same, and photometry such as color, normal or texture information, which do not affect the geometry of a mesh but affect the appearance of the mesh.
Face: A face is a set of vertex indices and a corner is a pair of (face, vertex) sets. A simple face is a set of vertex indices in which different indices form a face. In this invention, only a polygonal mesh consisting of simple faces will be dealt with.
Edge: A edge is a pair of vertex indices. If an edge appears on only one face in a polygonal mesh, the edge is defined as a xe2x80x9cboundaryxe2x80x9d edge. If one and the same edge appears on several faces, the edge is defined as a xe2x80x9csingularxe2x80x9d edge. If an edge appears on only two neighboring faces, the edge is defined as an xe2x80x9cinternalxe2x80x9d edge. The boundary edge and the internal edge are defined to be xe2x80x9cregularxe2x80x9d.
Mesh graph and dual graph: One point is defined within each face of a mesh and then points defined above and passing through the internal edge between neighboring faces are connected to be defined as a dual graph. FIG. 5A is a mesh graph and FIG. 5B is a dual graph.
Connected component: A path in a polygonal mesh is a series of non-recurrent vertices such as consecutive vertex pairs connected by one edge. The first and last vertices on a path are referred to as being connected by the path. If all pairs of the vertices of a triangular mesh are connected by one path, the triangular mesh is referred to as being connected. If a triangular mesh is not connected, the triangular mesh can be split into at least two connected components. Each connected component is a connected triangular mesh consisting of a subset of vertices, edges and triangles of the original triangular mesh. If two vertices of the triangular mesh are connected by one path, they belong to the same connected component.
Virtual reality modeling language (VRML): The VRML is a graphic standard format prepared for describing and transmitting a virtual space in the Internet.
Moving Picture Experts Group (MPEG): The MPEG is a group for carrying out international standardization activities for standardizing a compression format for transmitting a variety of media such as video.
Mesh: A mesh is a representation of an object constructed of several polygons.
Node: A node is a vertex in a vertex spanning graph or a minimum description unit used in VRML.
Topological surgery: A topological surgery is a mesh coding method proposed by I.B.M. Corp. in which a mesh is cut along a given path in order to make the mesh into the form of strips.
Vertex spanning graph: A vertex spanning graph is a path for cutting a mesh in the topological surgery.
Triangle spanning tree: The triangle spanning tree is a binary tree as a triangle strip produced by cutting a mesh along the vertex spanning graph
vrun: A vrun is a set of connected vertices and ends with a branch or vleaf.
vlast: A vlast indicates whether the current run is the last branch or not. If the current run is the last branch, the value of vlast is 1, and 0 otherwise.
vleaf: A vleaf indicates whether the current vertex run ends with a leaf or a branch. If the current vertex run ends with a leaf, the value of vleaf is 1, and 0 otherwise.
vlength is the length of a vertex run.
loopstart: The leaf of a vertex run may meet another vertex run to form a loop. In such a case, the start of the loop is indicated by the loopstart.
loopend: In the case when the leaf of a vertex run forms a loop, the end of the loop is indicated by the loopend.
loopmap: A loopmap indicates connectivity between the loopstart and the loopend and is a set of indices connecting edges from the loopend to the loopstart.
trun: A trun is a set of consecutive triangles and the end thereof is a leaf triangle or a branching triangle.
tleaf: A tleaf indicates whether the run of a triangle ends with a leaf triangle or a branching triangle. If the run of a triangle ends with a leaf triangle, the value of tleaf is 1, and 0 otherwise.
tmarching: A tmarching describes the marching aspect of triangles. If a strip has an edge at its right boundary, the value of tmarching is 1. If a strip has an edge at its left boundary, the value of tmarching is 0.
polygonedge: A polygonedge indicates whether a current edge is given from the original mesh model or inserted for representing the polygon as a set of triangles. If a current edge is given from the original mesh model, the value of polygonedge is 1, and 0, otherwise.
Torientation: A Torientation indicates whether the left or right side of the branching triangle is visited first. If the left side is visited first, 1 is given to the Torientation. If the right side is visited first, 0 is given.
In the conventional coding method of 3D mesh data, since the mesh data is wholly coded, it is almost impossible to partially restore data before an entire bitstream is received. Also, due to transmission path errors generated during transmission, even if only a part of the data is damaged, the entire bitstream of data must be received again. For example, ISO/IEC JTC1/SC29/WG11 MPEG-98/W2301, xe2x80x9cMPEG-4 SNHC Verification Model 9.0xe2x80x9d proposed by I.B.M. Corp. is currently being adopted as an MPEG-4 SNHC 3D mesh coding technology.
In MPEG-4 SNHC, mesh coding is designed based on VRML. In the VRML, a mesh is described in a node form referred to as an lndexedFaceSet. One of the main technologies for coding mesh data is a topological surgery proposed by I.B.M. Corp. According to this technology, it is assumed that a given mesh is the same as a sphere topologically. Then, the mesh is cut along a given cutting-edge to generate a triangle spanning graph having a binary tree structure. Here, the cutting-edge defined for cutting the mesh is configured such that it connects vertices, that is, it is given as a tree structure having a loop. The cutting-edge is referred to as a vertex spanning graph. Thus, two tree structures, that is, the triangle spanning graph and the vertex spanning graph, are coded/decoded, thereby restoring the original mesh without loss.
According to MPEG-4 SNHC, although there may be multiple IndexedFaceSets in a VRML file, compression is basically performed on the unit of one IndexedFaceSet. However, it is allowed to form a single IndexedFaceSet by several connected components.
In general, for fast graphics processing, modeling must be performed in units of triangles. These triangles are not formed randomly but are preferably connected to each other in the form of strips or fans. Also, the more symbols that are repeatedly represented, the better the compressibility is. To this end, a mesh formed by a single long triangular strip is proposed by I.B.M. Corp. in view of fast graphics processing and better compressibility.
FIG. 1 illustrates an example of a vertex spanning graph having a loop in which a vertex run returns to one of the passed vertices.
FIGS. 2A through 2F illustrate a conventional method for generating a vertex spanning graph and a triangle spanning graph in an example of a triangular mesh. In FIGS. 2A, 2B, 2C and 2D, the vertex spanning graph is drawn by a thick line, which may branch off into several branches from one branch. A mesh is cut along the vertex spanning graph to obtain a long connected triangular strip, which is referred to as a triangle spanning graph, as shown in FIG. 2C. FIG. 2E shows a procedure for generating a bounding loop formed by the vertex spanning graph, and FIG. 2F shows a dual graph. The dual graph shown in FIG. 2F is obtained by connecting an arbitrary point within a triangle and a point within another triangle next to the triangle via the edge of the triangle. In the case of a triangle spanning graph, the dual graph has a binary tree structure.
Since a mesh can be formed by several connected components, each connected component forming the mesh generates a pair of a vertex spanning graph shown in FIG. 2B and a triangle spanning graph shown in FIG. 2C. Therefore, if a single IndexedFaceSet is coded, several triangle spanning graphs and vertex spanning graphs can be obtained.
The method for restoring the data coded by the above-described method is as follows:
1. A bounding loop shown in FIG. 3 is generated using a vertex spanning graph.
2. When the third vertex of a triangle branching off in a triangle spanning tree is referred to as a Y-vertex, the Y-vertex is calculated using bitstreams of the triangle spanning tree.
3. Triangles or polygons are generated using a triangle marching bit of the triangle spanning graph.
Lossless compression using arithmetic coding of the vertex spanning graph and the triangle spanning graph has been proposed by I.B.M. Corp. However, according to this method, in order to reconstruct the original structure, all bitstreams must be input and the following problems arise:
1. Since all bitstreams are necessarily input for decoding data, in any event of a transmission error, all bitstreams must be retransmitted.
2. In the case when the magnitude of compressed data is large, it takes a long time to transmit the data completely and a user must wait during such a time.
To overcome the disadvantages of the conventional technology, the following functions must be satisfied.
1. Even if a transmission error is generated, only the portion having the transmission error need be retransmitted, thereby reducing the network load and the transmission time.
2. Restoration is allowed in which only a part of the data and triangles or polygons for the restored portion are processed to be displayed on a screen.
Implementation of these two functions while maintaining the basic structure of the conventional method proposed by I.B.M. Corp. depends on effective processing of the bounding loop and Y-vertex, as shown in FIG. 3. In order to calculate the Y-vertex in a restoration process, at least one of two branching triangle runs must be received. In FIG. 2F, points 10, 14 and 18 are Y-vertices. For triangles within a triangle run, indices for the three vertices of each triangle can be determined using the marching bit pattern and the bounding loop. However, in order to determined the indices of Y-vertices which are the third vertices of branching triangles, all bitstreams for another two triangle runs next to the branching triangles must be received. Therefore, the triangles next to the branching triangles cannot be restored to be displayed until subsequent bitstreams are received. This problem is not generated in the method proposed by I.B.M. Corp., which is based on the assumption that all bitstreams are received. However, in order to restore and display the triangles in the input order, this problem must be solved.
FIG. 6 is a conceptual block diagram of a conventional three-dimensional (3D) mesh information coding method. In FIG. 6, a 3D mesh object 100 is divided into connectivity, geometry and photometry and coded by a coding part 101 including a connectivity coder 102, a geometry coder 103 and a photometry coder 112. Here, vertex structure information 105 is transmitted from the connectivity coder 102 to the geometry coder 103. The information compressed by the connectivity coder 102, the geometry coder 103 and the photometry coder 112 is replaced to bitstream 111 compressed by an entropy coder 104.
The compressed bitstream 111 is input to a decoding part 112. In other words, the compressed bitstream 111 is divided into connectivity, geometry and photometry via an entropy decoder 106 to then be decoded by a connectivity decoder 107, a geometry decoder 108 and a photometry decoder 113, respectively. Like in the coding part 101, vertex structure information 109 is transmitted from the connectivity decoder 107 to the geometry decoder 108. A decoded 3D mesh object 110 can be constructed using the decoded connectivity, geometry and photometry.
In FIG. 6, a 3D mesh can be transmitted in forms of compressed bitstreams in a communication path. However, since the conventional MPEG data compression method employs the entropy coder 104, the method is weak against transmission errors generated in a communication path.
To solve the above problems, it is an objective of the present invention to provide a method for progressively coding/decoding 3D mesh information, by which a network load and a transmission time can be reduced by re-transmitting only a part where a transmission error is generated and the 3D mesh information can be progressively restored using connectivity, geometry and photometry of the transmitted part.
Accordingly, to achieve the above objective, there is provided a progressive coding method of three dimensional (3D) mesh information comprising the steps of: (a) dividing a 3D triangle mesh of a model into one or more connected components; (b) generating a vertex graph and a triangle graph for each of the connected components; (c) partitioning the vertex graph and triangle graph constituting the connected components into data partitions each capable of being independently decoded for the respective connected components and then coding the same; (d) coding geometry containing positions of vertices of triangles constituting each partition, and photometry containing color, normal and texture coordinate information, for the respective data partitions.
According to another aspect of the present invention, there is provided a progressive decoding method for receiving bitstreams coded by a progressive coding method comprising the steps of: (a) dividing input bitstreams into units of data partitions; (b) identifying the partition type of each of the data partitions; (c) if the data partitions contain vertex graphs, decoding the vertex graphs to generate bounding loops; (d) if the data partitions contain triangle graphs, decoding the triangle graphs to generate a 3D mesh; and (e) repeating the steps (a) through (d) to progressively generate 3D meshes.